package com.heima.leetcode.practice;

/**
 * leetcode 518. 零钱兑换 II
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/11 13:05
 */
public class E518 {
    /*
            0    1    2    3    4    5    amount
        1   0    1    11   111  1111 11111

        2   0    1    11   111  1111 11111
                      2    21   211  2111
                                22   221

        5   0    1    11   111  1111 11111
                      2    21   211  2111
                                22   221
                                     5
        其中dp[i][j]表示使用前i种硬币，组成总金额为j的所有组合数
        if (当前面额大于总金额){
            dp[i][j] = dp[i-1][j] // 当前面额无法参与，所以和前0 - i-1个凑法一致
        } else if (当前面额等于总金额){
            dp[i][j] = dp[i-1][j] + 1; // 当前面额刚好组成总金额，所以其它和前i-1个凑法一致，再加1即可
        } else {
            dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]] // 当前面额小于总金额，可以参与组成总金额，加上前0 - i-1个凑法，然后选取一个当前面额，剩余的部分继续用0-i的面额进行凑
        }
     */

    /**
     * <h3>方法一：动态规划，二维数组</h3>
     *
     * @param amount 总金额
     * @param coins  硬币面额
     * @return 凑出总金额的组合数
     */
    public int change1(int amount, int[] coins) {
        // 1. 构建二维数组
        int rows = coins.length;
        int columns = amount + 1;
        int[][] dp = new int[rows][columns];
        // 2. 对dp数组的第一行进行初始化，第一列都设置为1，因为题目要求是凑0的组合数是1
        for (int i = 0; i < rows; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; j < columns; j++) {
            if (j < coins[0]) { // 面额不够，凑不了，凑法为0
                dp[0][j] = 0;
            } else if (j == coins[0]) { // 刚好凑出，凑法为1
                dp[0][j] = 1;
            } else { // 拿走一个面额还有剩余，继续凑剩下的金额
                dp[0][j] = dp[0][j - coins[0]];
            }
        }
        // 3. 对dp数组的其他行进行初始化
        for (int i = 1; i < rows; i++) {
            int currCoin = coins[i];
            for (int j = 0; j < columns; j++) {
                if (j < currCoin) { // 当前面额不够，凑不了，凑法为前0 - i-1个硬币的凑法
                    dp[i][j] = dp[i - 1][j];
                } else if (j == currCoin) { // 刚好够，说明比前面0 - i-1个硬币的凑法多一个
                    dp[i][j] = 1 + dp[i - 1][j];
                } else { // 拿走一个面额还有剩余，用前0-i个面额凑剩余的金额 加上前0 - i-1个硬币的总凑法
                    dp[i][j] = dp[i - 1][j] + dp[i][j - currCoin];
                }
            }
        }
        // 4. 返回dp数组右下角
        return dp[rows - 1][columns - 1];
    }

    /**
     * <h3>方法二：动态规划，一维数组</h3>
     *
     * @param amount 总金额
     * @param coins  硬币面额
     * @return 凑出总金额的组合数
     */
    public int change2(int amount, int[] coins) {
        // 1. 构建二维数组
        int[] dp = new int[amount + 1];
        // 2. 对dp数组的第一行进行初始化，第一列都设置为1，因为题目要求是凑0的组合数是1
        dp[0] = 1;
        // 3. 对dp数组的其他行进行初始化
        for (int coin : coins) {
            for (int j = 0; j < dp.length; j++) {
                if (j >= coin) { // 拿走一个面额还有剩余，用前0-i个面额凑剩余的金额 加上前0 - i-1个硬币的总凑法
                    dp[j] = dp[j] + dp[j - coin];
                }
            }
        }
        // 4. 返回dp数组右下角
        return dp[amount];
    }

    /**
     * <h3>方法三：动态规划，一维数组，进一步优化</h3>
     *
     * @param amount 总金额
     * @param coins  硬币面额
     * @return 凑出总金额的组合数
     */
    public int change3(int amount, int[] coins) {
        // 1. 构建二维数组
        int[] dp = new int[amount + 1];
        // 2. 对dp数组的第一行进行初始化，第一列都设置为1，因为题目要求是凑0的组合数是1
        dp[0] = 1;
        // 3. 对dp数组的其他行进行初始化
        for (int coin : coins) {
            for (int j = coin; j < dp.length; j++) {
                dp[j] = dp[j] + dp[j - coin];
            }
        }
        // 4. 返回dp数组右下角
        return dp[amount];
    }
}
